n=10000;
m=1000;
k=82;
tube=[|7642,738,801|
233,195,299|
7385,344,847|
6308,531,704|
6161,641,900|
7343,78,772|
829,0,872|
9647,983,992|
3201,644,683|
8294,100,173|
1517,665,683|
3334,15,196|
3043,198,402|
3781,331,489|
8192,524,981|
6052,537,655|
6278,155,727|
692,988,993|
3997,800,999|
1365,94,108|
9511,417,795|
4122,9,310|
9910,900,992|
8000,591,883|
7748,513,793|
1516,201,268|
3335,935,951|
3621,823,910|
6159,786,905|
2878,469,837|
6831,807,847|
8799,977,990|
221,737,772|
2715,587,949|
2165,621,798|
4101,637,889|
8237,278,362|
9653,261,368|
8816,289,698|
1318,290,721|
8268,800,926|
4918,487,528|
9768,365,877|
9491,352,802|
8964,779,862|
1606,609,731|
2577,660,715|
6274,89,709|
446,320,605|
9118,438,707|
6881,254,309|
7214,187,981|
4501,962,964|
1642,484,507|
7133,343,667|
3529,489,549|
2834,407,458|
5170,313,937|
9085,187,629|
8244,98,158|
8008,234,482|
968,402,453|
4449,580,906|
6891,944,957|
9973,645,651|
4363,459,766|
1259,306,435|
6156,464,630|
5854,913,918|
3712,943,972|
8526,564,644|
886,295,807|
3978,622,649|
916,912,956|
7142,237,534|
1465,96,339|
8732,379,749|
3211,467,765|
2130,168,452|
3121,801,833|
2757,526,745|
3770,315,880|];
X=[2,6,2,2,3,5,9,5,4,6,1,4,3,1,6,4,5,1,4,5,5,4,1,6,7,1,8,9,7,4,3,3,3,7,3,2,8,6,9,9,9,2,8,8,5,2,3,2,7,1,6,3,3,2,7,6,7,4,5,8,7,4,1,4,8,4,2,8,1,6,8,2,7,8,1,8,1,7,4,7,1,6,2,6,1,5,9,2,7,3,2,5,9,9,9,9,2,2,6,3,4,4,2,6,2,6,6,1,8,3,1,5,5,5,1,4,3,3,9,1,4,8,3,2,4,6,4,6,4,7,4,3,4,8,9,1,3,3,2,4,6,7,9,4,9,2,8,7,5,3,2,8,6,9,1,9,9,2,8,6,3,6,9,9,5,8,8,2,3,8,9,3,5,5,7,5,6,5,3,6,8,3,6,8,9,5,3,7,9,5,7,1,8,1,4,4,7,6,5,5,7,3,6,2,4,8,3,7,3,7,3,5,3,7,2,9,1,5,7,8,9,8,4,8,3,7,1,2,8,8,1,3,7,4,8,2,5,5,4,9,3,9,3,2,1,6,4,5,2,9,7,3,9,5,5,7,7,8,8,9,6,2,9,6,3,7,3,7,3,3,4,5,6,2,9,5,3,9,2,9,6,2,3,1,7,1,1,2,3,6,8,4,5,9,4,1,2,9,6,7,1,2,7,4,2,6,8,6,7,7,8,2,4,2,7,8,1,5,1,2,6,6,2,5,1,9,4,6,8,3,8,1,8,3,3,5,6,1,7,6,2,4,2,9,1,3,2,7,5,6,7,1,7,1,1,2,9,4,8,7,4,8,2,2,1,8,4,9,5,5,6,3,4,1,3,2,5,6,2,7,1,6,9,3,4,4,8,9,6,2,5,3,9,4,2,9,2,4,7,2,1,6,7,6,1,8,8,2,5,4,9,6,3,8,4,8,7,8,4,2,9,4,6,9,6,5,4,3,8,4,5,5,1,2,5,4,2,8,2,6,8,8,8,7,7,7,1,9,9,3,5,5,5,1,6,6,4,4,3,5,9,8,8,9,7,7,7,3,1,3,7,7,1,8,7,2,9,5,3,1,3,6,4,8,7,5,4,9,9,6,6,3,1,1,7,8,3,8,8,6,2,6,9,7,6,2,6,6,7,7,3,2,6,7,2,8,3,4,3,7,3,1,6,3,8,2,2,1,8,9,7,7,7,8,8,5,6,4,7,2,1,3,4,7,7,6,1,1,1,2,8,4,1,6,9,1,6,9,2,9,7,9,7,3,5,3,8,5,8,4,3,5,4,7,5,9,9,6,6,1,1,9,4,5,7,7,9,7,3,4,5,8,1,8,1,3,7,5,2,2,3,7,8,7,3,8,3,9,8,4,3,5,5,6,2,3,2,1,8,9,7,6,9,7,8,2,3,8,2,2,7,5,9,7,4,8,9,5,4,3,7,8,7,3,6,9,2,8,8,7,8,7,4,3,8,6,6,8,8,6,8,4,6,9,4,1,7,5,2,5,6,9,2,9,3,8,7,1,8,4,2,9,4,8,4,2,1,9,2,7,1,5,3,7,9,8,7,8,4,5,4,7,9,3,9,3,1,2,7,8,4,4,6,1,3,7,4,9,6,2,7,9,9,7,6,2,5,9,4,8,7,2,4,9,7,1,3,8,1,7,4,4,3,6,8,9,8,2,6,1,9,3,8,9,9,4,4,1,6,7,8,6,4,6,4,8,3,9,6,5,5,7,2,1,9,7,2,1,6,1,8,9,6,5,7,5,4,7,5,7,1,8,5,4,2,9,1,6,5,6,5,9,2,1,9,6,1,7,1,4,3,7,9,8,8,1,4,2,2,8,5,8,6,6,2,4,9,6,8,7,4,6,6,9,5,6,7,8,4,5,3,6,4,8,2,5,3,8,4,4,8,3,1,6,2,7,4,4,1,6,4,2,9,1,1,8,1,2,7,1,4,1,5,3,3,4,7,1,1,6,3,5,1,9,9,3,2,7,4,9,6,3,7,5,2,2,1,6,9,3,3,1,6,1,4,4,2,9,7,8,1,8,5,5,7,2,2,3,4,3,9,3,1,6,2,2,2,6,2,6,7,5,2,8,6,1,6,3,1,9,8,8,5,1,4,9,9,4,7,6,1,6,5,1,3,4,7,7,4,4,2,3,5,1,6,9,8,8,9,5,3,9,7,6,1,6,1,9,3,2,3,8,2,1,2,9,1,1,2,7,4,9,9,2,3,6,8,2,7,7,3,7,2,9,9,1,4,2,4,2,3,9,7,6,9,8,5,3,8,5,3,7,2,8,6,7,9,4,3,6,1,2,6,8,4,8,5,8,6,7,1,5,8,4,6,1,1,8,3,8,7,8,9,7,1,5,6,8,7,2,9,5,1,5,5,5,7,3,5,8,8,1,8,3,7,4,4,4,6,4,2,2,7,1,6,4,9,4,1,8,8,2,7,3,4,2,7,8,2,1,5,7,6,7,4,2,4,3,7,6,4,1,6,3,6,1,5,8,5,2,5,9,3,4,2,6,3,1,2,5,2,1,8,2,1,9,4,8,7,2,7,8,1,8,9,4,4,4,1,2,8,2,9,5,9,1,1,3,8,7,9,6,2,9,3,8,1,9,8,2,4,8,9,9,8,9,2,4,3,1,2,3,7,7,1,8,6,6,4,9,7,2,2,1,4,8,7,3,7,5,3,1,4,2,7,4,6,4,6,9,9,2,4,6,8,6,9,6,8,7,2,9,2,3,9,4,6,1,5,8,3,9,8,3,8,1,6,5,6,9,8,3,3,9,5,8,8,6,8,7,4,1,4,4,2,3,3,9,4,8,3,1,8,3,3,7,5,3,3,4,6,9,7,6,4,4,7,3,7,9,2,1,3,1,6,5,8,3,8,1,3,6,3,6,1,5,9,7,6,5,9,9,9,7,1,6,4,2,8,3,9,6,8,8,8,3,8,9,4,1,8,5,6,5,1,7,1,5,4,9,2,4,2,9,4,4,4,8,1,6,8,7,5,6,9,6,4,5,1,5,1,2,4,9,1,1,6,4,4,5,9,9,5,6,5,5,5,6,3,6,8,1,2,1,1,4,1,1,8,8,9,5,8,8,4,2,8,5,4,7,7,9,5,3,1,1,1,2,5,4,9,7,5,9,5,9,6,5,5,8,3,1,3,6,7,2,5,7,6,5,9,9,8,3,5,4,6,8,4,8,2,1,4,4,1,8,2,9,5,1,7,6,6,8,4,6,2,9,2,2,1,8,3,8,6,4,2,3,7,3,3,4,4,6,4,5,5,3,6,1,1,1,1,4,2,6,4,5,9,9,6,7,3,4,9,9,5,8,1,7,8,2,2,5,5,3,4,9,5,3,3,1,9,7,6,9,5,1,6,4,5,7,1,1,6,7,3,2,2,8,2,8,5,1,3,6,7,2,6,2,2,7,4,3,5,3,5,3,8,7,5,1,6,7,8,2,5,9,7,2,9,6,2,3,8,5,9,1,5,5,4,8,3,4,8,6,8,8,7,6,5,4,3,7,9,6,5,1,9,4,9,2,9,4,5,1,7,4,6,3,9,5,1,2,6,5,3,8,2,9,7,4,8,1,3,4,9,5,1,8,9,1,5,2,6,7,3,4,5,3,2,6,3,9,5,8,6,2,9,2,7,5,7,8,5,7,6,7,3,7,2,7,6,4,4,7,5,8,7,2,5,5,8,3,6,5,8,1,3,7,1,3,3,4,5,6,1,6,1,6,5,2,6,5,4,3,2,4,2,9,9,4,4,3,5,8,4,8,7,6,9,3,9,1,9,5,9,1,3,4,8,3,7,9,1,2,9,4,6,5,8,7,4,4,1,2,5,6,9,3,6,5,2,9,7,7,9,9,9,8,8,3,9,9,3,6,2,2,4,5,9,3,4,1,1,7,3,7,6,1,6,7,9,5,4,1,2,5,9,1,8,7,4,3,8,6,4,7,6,1,2,6,8,1,4,6,7,3,2,9,4,1,6,8,9,5,5,9,8,7,1,2,1,5,7,5,6,7,3,7,9,8,9,6,6,9,3,9,2,7,5,6,5,8,3,5,4,5,8,1,8,6,5,6,9,8,3,1,4,1,9,7,4,4,7,2,6,3,2,1,6,8,3,3,3,1,6,2,6,6,7,5,2,9,1,9,7,4,2,2,8,2,5,6,8,2,7,3,2,8,8,6,1,1,5,3,7,1,5,9,7,3,5,8,3,3,9,3,6,8,1,1,1,4,5,6,9,4,1,5,6,9,2,2,3,5,5,5,3,7,8,7,7,8,8,6,6,6,5,3,2,7,9,5,7,8,3,3,2,3,9,1,8,9,6,9,7,8,5,7,3,7,3,1,5,1,6,8,9,5,8,9,6,7,5,3,4,8,4,6,6,1,3,8,2,5,3,1,6,8,7,5,5,3,6,5,4,8,8,6,5,5,2,5,8,5,2,3,1,3,3,6,7,9,6,2,3,8,7,8,3,7,9,8,1,4,2,6,8,1,7,2,1,1,8,7,6,3,7,1,5,8,8,4,3,6,8,6,3,4,9,9,1,6,5,2,5,5,7,6,7,7,5,3,7,4,3,7,9,7,4,2,4,8,2,9,9,3,7,7,9,7,8,9,9,7,3,8,3,6,4,3,7,3,8,5,8,5,9,9,8,2,1,4,9,4,1,1,7,6,4,8,7,2,4,5,3,1,8,1,9,5,8,2,9,8,5,7,5,6,8,6,2,9,5,5,2,1,3,3,6,9,1,1,6,9,6,9,6,4,4,1,6,3,1,8,9,5,2,3,1,6,2,8,9,3,6,6,2,7,9,7,8,6,4,5,7,5,4,1,1,2,4,5,2,6,3,7,1,5,9,4,6,3,9,8,5,3,3,2,7,5,6,5,3,7,5,7,7,7,1,4,9,2,2,6,5,7,7,2,7,8,6,9,9,8,5,3,4,6,2,4,7,4,6,9,1,2,7,7,3,7,1,2,7,5,6,1,6,4,4,3,8,8,3,1,4,9,9,3,7,1,5,3,1,7,8,8,9,7,6,2,2,1,2,5,9,9,4,9,6,5,4,8,4,9,1,5,8,8,5,4,6,5,9,1,7,9,6,8,8,8,5,5,6,8,5,2,2,8,7,5,2,3,5,4,6,8,9,1,6,4,8,9,7,6,1,7,8,6,8,5,8,2,3,1,7,7,6,8,8,5,1,9,9,8,2,9,3,4,9,9,5,7,8,8,7,4,3,3,5,7,1,3,7,3,8,1,5,6,1,7,4,2,1,6,2,8,6,7,5,5,8,2,1,3,7,6,6,5,7,7,8,6,4,5,2,7,2,9,3,7,7,8,6,6,8,1,4,1,7,2,9,3,4,8,9,3,6,7,2,3,2,6,7,8,6,8,4,3,8,3,2,1,3,5,6,4,6,8,1,2,2,6,6,2,5,8,4,7,4,8,5,5,6,1,5,7,7,9,8,4,9,4,7,7,8,2,2,8,5,8,5,3,5,9,1,9,9,1,9,8,9,5,1,5,8,2,5,1,7,6,1,3,4,4,1,5,8,8,7,9,4,3,4,2,1,3,8,5,7,7,8,3,6,2,3,3,7,1,6,8,5,2,5,9,3,4,5,6,6,1,1,2,8,8,3,5,6,8,9,5,4,2,3,7,7,4,8,5,4,5,8,8,3,7,2,9,7,8,3,8,1,5,4,2,8,1,3,5,3,2,1,6,9,6,7,9,2,3,9,9,5,2,8,5,6,2,5,9,8,5,5,7,4,9,8,7,6,5,3,2,4,9,7,3,9,6,9,6,1,1,1,9,4,7,9,9,6,1,3,4,8,9,9,5,7,6,8,9,4,5,1,5,7,7,5,8,7,6,8,6,2,8,2,8,3,4,4,5,1,6,1,5,7,5,7,7,6,3,2,8,8,2,9,7,7,2,5,3,3,6,4,1,7,4,8,7,3,5,3,6,3,3,8,9,1,3,5,1,1,7,4,2,9,5,6,5,3,4,3,7,3,2,8,6,3,5,2,8,1,6,9,3,8,2,5,6,2,2,6,7,5,2,6,3,8,1,7,8,5,9,3,5,1,3,2,4,6,8,2,7,4,6,6,1,1,7,1,5,8,6,2,1,2,6,4,8,5,5,5,1,9,6,7,2,2,9,4,6,6,3,2,4,3,7,8,1,4,5,1,4,8,2,1,4,9,3,4,6,9,9,8,9,2,8,6,1,9,4,8,5,1,6,8,7,3,2,5,6,1,4,1,2,4,7,1,7,6,2,1,8,2,8,6,9,5,1,5,3,5,8,9,2,1,5,7,8,8,4,6,5,2,2,5,1,9,1,8,8,2,5,4,7,5,8,1,8,6,4,9,8,9,4,7,1,3,6,4,1,2,5,1,9,8,6,4,1,1,5,1,2,8,4,8,7,2,5,1,5,4,8,2,5,7,5,2,8,9,6,6,2,2,6,7,4,1,3,8,9,4,1,5,1,2,1,6,1,6,4,4,2,7,2,2,7,2,5,5,1,7,1,8,5,5,8,2,1,2,8,9,5,9,5,2,7,3,7,4,4,7,6,8,3,4,9,4,2,1,6,1,6,6,9,2,6,2,2,2,6,5,5,6,9,2,3,4,8,6,6,8,1,9,5,4,3,1,2,4,7,4,1,3,4,4,3,9,8,9,7,7,6,8,2,6,3,5,2,9,3,5,4,3,8,9,3,4,9,4,6,6,5,1,5,2,1,7,4,2,1,5,3,9,3,8,1,6,2,3,1,8,4,3,2,8,8,3,5,7,3,3,7,8,9,1,1,6,2,8,7,4,3,1,4,2,2,6,9,5,1,3,3,9,4,7,2,2,5,9,1,2,2,7,7,6,6,4,5,2,8,6,7,2,7,5,7,6,9,9,4,2,2,7,9,2,3,3,9,5,9,2,2,3,9,5,4,9,2,6,9,4,9,8,5,3,1,6,1,8,9,9,9,4,9,7,2,6,2,7,5,7,2,3,1,8,2,8,3,7,7,6,2,7,2,6,1,6,4,2,6,7,5,4,2,5,2,3,8,3,1,3,8,1,3,9,1,4,8,8,3,4,9,4,3,2,9,3,8,5,2,9,7,2,3,9,2,6,4,4,3,8,7,6,8,5,2,6,9,8,5,4,6,5,8,6,3,7,2,2,2,6,4,5,4,1,9,5,2,5,7,6,2,5,5,9,9,3,2,2,2,2,7,3,4,4,7,7,2,6,6,7,5,6,6,8,9,3,5,1,1,5,2,1,9,6,1,8,9,8,8,9,3,7,6,1,9,2,3,2,6,7,4,7,4,5,8,5,3,5,7,2,8,3,1,1,6,9,7,1,9,1,7,5,3,5,3,2,4,7,5,9,1,9,4,6,3,8,7,1,1,7,8,2,3,4,4,7,8,8,1,2,6,4,1,9,4,2,4,1,7,9,7,1,7,4,3,2,2,6,4,2,7,6,2,3,1,6,6,2,5,8,7,1,9,8,9,7,8,5,9,7,6,5,7,1,6,7,4,9,9,4,1,3,2,3,2,7,7,7,2,7,1,8,5,3,8,1,4,2,7,1,1,4,6,9,3,3,6,5,4,3,1,7,4,5,2,7,8,5,8,7,8,2,8,2,1,2,4,9,7,8,5,4,4,3,3,3,6,9,7,5,1,3,5,9,2,5,8,3,5,5,2,3,9,9,7,9,8,9,2,1,4,3,2,2,7,8,9,2,9,9,1,2,1,6,7,8,9,8,4,4,2,5,9,6,1,1,4,4,1,8,6,4,6,2,9,6,5,8,3,6,6,8,8,6,2,2,9,8,5,7,4,9,3,8,1,4,8,2,2,1,3,7,5,9,4,2,7,1,6,8,2,2,8,4,1,2,3,7,1,6,6,6,4,8,3,5,3,2,6,1,6,3,4,4,9,3,5,6,1,6,3,5,4,3,6,1,8,5,6,4,6,8,8,5,1,1,9,5,6,8,6,8,5,4,8,4,6,8,2,2,8,3,1,6,4,4,8,2,4,1,9,1,5,7,8,4,6,2,3,2,9,3,5,5,6,5,9,8,2,4,1,5,9,2,2,5,5,3,9,4,9,8,1,6,6,7,3,9,6,9,8,3,7,8,9,3,5,3,3,4,6,1,1,8,5,8,8,2,1,1,7,4,8,6,3,5,7,7,3,9,9,8,2,9,6,7,9,3,4,4,5,6,8,2,4,4,4,4,6,4,9,1,8,2,1,7,1,9,1,5,9,1,7,5,5,2,7,1,4,5,6,4,9,9,3,2,9,2,4,6,1,2,6,7,3,1,2,7,6,9,6,8,8,9,2,9,2,4,1,4,1,5,5,9,4,6,4,4,9,1,6,9,6,9,3,4,4,2,6,6,6,5,2,9,9,8,5,8,7,4,8,9,2,8,6,9,2,6,1,9,1,8,1,5,1,4,1,1,8,4,9,3,6,3,9,9,7,2,1,4,9,9,7,7,5,6,9,3,2,7,5,5,8,7,9,8,3,4,2,9,4,6,8,6,9,8,4,1,7,7,4,1,6,4,9,9,6,5,9,3,9,7,2,1,3,2,6,2,2,8,6,9,1,5,1,1,3,7,2,9,8,9,9,6,3,7,9,7,8,2,4,5,6,6,5,7,3,4,2,1,9,9,2,1,5,5,1,2,8,9,1,1,6,4,1,7,9,4,9,7,4,9,8,6,3,5,6,4,7,7,7,3,8,2,9,9,7,3,3,8,8,6,4,2,5,4,7,3,2,1,2,9,3,1,7,8,7,6,2,6,3,3,3,3,8,1,7,3,4,4,4,3,4,8,2,6,9,9,3,4,1,5,6,6,5,7,8,7,4,2,5,4,3,7,2,3,1,7,9,4,9,3,6,5,9,9,2,7,2,7,2,1,3,4,8,4,5,3,1,5,3,3,3,6,1,3,9,9,5,2,5,8,7,6,6,4,3,1,3,6,7,9,4,6,6,9,8,8,4,9,2,6,4,8,9,6,8,1,9,9,2,2,2,3,1,9,9,4,8,6,2,3,3,8,7,9,1,5,7,2,3,5,4,3,7,1,8,3,3,5,5,3,5,3,2,7,3,6,7,9,6,9,7,8,9,5,5,4,3,1,8,6,7,5,6,6,8,2,2,1,7,2,7,1,9,2,7,6,7,6,3,3,5,4,8,5,4,5,9,1,5,4,9,2,1,7,9,1,8,7,5,8,6,7,6,9,7,9,3,8,8,1,9,6,3,1,5,2,8,1,2,1,4,1,8,3,7,6,2,2,4,8,7,4,6,4,3,3,9,5,6,6,1,7,3,4,2,1,9,8,5,7,2,8,6,6,8,3,2,5,8,9,6,3,9,3,8,6,5,1,3,1,5,6,9,8,5,3,3,2,2,9,2,7,5,3,7,5,1,6,6,3,7,1,5,6,6,2,8,2,1,7,4,7,9,9,3,6,5,6,6,4,5,5,1,1,8,6,8,2,4,2,1,1,9,3,4,3,8,6,2,6,3,6,4,3,6,7,7,6,2,9,2,1,7,3,7,6,7,5,7,3,8,4,7,1,6,1,7,5,9,2,2,3,7,6,2,2,6,3,1,6,8,1,9,8,8,4,5,6,8,2,8,7,2,3,8,5,1,1,6,8,5,2,2,8,6,7,8,5,9,9,4,1,8,5,6,6,8,8,2,1,2,7,7,7,7,8,7,5,8,4,8,2,4,4,9,1,7,8,7,5,7,4,1,6,4,7,7,6,2,4,9,9,7,7,8,7,2,7,3,5,1,6,3,7,5,4,1,9,8,8,3,6,8,1,4,6,9,7,9,6,1,5,1,3,5,7,1,4,4,7,4,8,3,2,5,1,3,1,6,4,1,1,4,5,3,2,5,4,8,6,1,8,1,2,9,9,6,6,1,2,1,6,6,2,2,7,1,2,1,2,8,5,7,9,9,7,7,4,7,7,7,6,3,3,8,1,2,8,4,1,3,1,3,3,3,4,6,5,5,9,7,6,3,3,6,7,4,5,6,4,2,6,3,5,5,5,2,6,1,9,8,2,1,8,2,2,5,7,5,9,1,6,1,5,7,5,5,4,8,6,1,9,1,8,3,7,7,3,2,5,5,1,9,2,2,5,3,3,5,6,1,6,4,2,1,1,9,3,3,4,9,2,8,1,9,8,6,5,9,1,6,1,9,2,4,2,2,1,4,9,4,7,8,5,2,5,3,1,6,9,3,8,8,1,8,9,5,6,4,8,3,9,4,2,8,7,6,3,1,3,1,5,4,5,7,9,4,2,4,4,9,1,1,7,1,4,5,3,7,3,9,2,6,5,2,7,5,5,7,2,5,6,9,6,3,6,6,1,5,7,1,4,8,6,5,7,9,8,9,1,1,1,8,2,9,3,7,3,2,5,2,5,4,3,6,8,4,7,5,2,5,2,8,3,7,5,5,5,9,7,5,7,9,9,1,3,2,2,5,7,7,9,8,8,9,8,5,1,5,3,6,5,7,5,6,5,9,2,5,1,9,4,8,4,3,3,8,4,9,7,4,3,5,5,2,9,8,1,6,5,5,4,3,7,9,2,4,5,6,5,1,5,7,3,4,5,4,1,2,6,9,3,9,1,4,9,8,1,3,2,8,2,3,6,7,4,2,9,8,1,2,2,9,1,2,6,6,7,9,9,7,9,4,7,6,8,7,4,1,6,2,6,6,1,2,8,7,7,5,7,1,4,5,9,7,3,2,3,7,1,9,2,2,2,9,3,3,4,9,8,3,4,5,9,6,5,3,6,3,8,5,8,5,1,3,7,4,5,4,5,1,9,2,6,2,4,3,6,2,8,7,4,1,5,3,8,5,4,9,6,2,9,6,8,5,6,6,3,7,7,4,8,7,8,7,9,8,2,8,7,1,5,2,9,1,4,8,6,2,6,5,4,1,6,9,2,4,5,8,1,7,8,4,5,5,1,1,2,4,6,7,2,8,2,5,4,4,2,2,9,2,6,8,9,1,2,8,4,4,1,5,5,2,1,7,8,4,5,7,8,4,3,9,6,8,4,8,4,9,9,1,9,7,1,1,1,5,2,4,9,8,1,8,1,6,1,5,6,6,5,1,8,2,5,4,5,5,6,8,6,4,6,2,7,3,4,2,4,8,8,2,2,4,5,8,2,6,7,5,1,3,8,2,5,8,9,2,2,3,3,3,1,8,2,9,6,4,5,2,4,1,5,9,2,7,1,7,6,7,5,7,6,1,2,8,8,2,3,6,7,8,4,5,6,5,3,7,7,7,6,9,6,5,8,1,4,2,1,7,3,1,1,4,9,4,9,7,2,9,9,2,7,8,4,8,2,1,2,7,9,4,9,9,7,5,6,7,6,7,8,5,1,9,5,1,3,1,7,6,6,5,6,4,6,8,1,2,4,8,3,1,7,5,5,5,9,9,9,3,8,7,7,4,7,4,7,3,9,5,6,2,7,5,1,9,6,2,2,1,3,7,4,2,5,3,4,1,2,2,3,5,4,6,7,3,5,4,6,7,9,6,9,6,9,1,6,3,7,1,9,8,7,8,5,9,9,9,7,7,9,1,7,1,8,3,2,9,8,7,9,9,1,3,1,9,4,3,1,3,8,2,4,4,5,9,5,5,4,1,6,1,4,8,1,8,3,6,7,3,8,1,7,6,1,2,1,4,3,6,9,1,1,6,4,6,6,9,6,9,6,1,8,6,3,3,1,1,6,5,3,6,2,6,8,4,2,6,5,6,1,6,8,8,1,9,1,6,7,7,3,5,9,8,3,8,8,2,9,7,1,9,7,1,3,5,3,2,1,5,9,5,4,3,2,1,3,2,8,9,5,1,2,9,9,3,3,4,7,7,3,1,2,2,9,8,1,1,1,1,9,3,6,5,3,9,6,7,7,4,4,9,1,5,5,3,5,3,2,9,5,8,5,5,1,7,8,6,9,2,2,5,9,5,7,3,2,1,3,6,1,3,3,5,4,5,1,9,9,9,5,6,1,8,1,2,2,6,9,3,5,7,2,2,6,5,8,3,5,8,9,3,9,1,7,7,6,4,6,4,9,9,4,2,7,2,5,3,9,7,1,6,4,2,1,8,8,4,7,1,3,8,3,8,8,5,8,3,8,9,4,5,3,4,9,1,9,5,3,8,7,7,4,4,9,7,8,3,6,4,4,5,8,1,2,8,9,6,2,1,8,9,5,2,4,4,7,8,4,3,4,6,5,5,9,4,1,1,4,2,5,3,9,3,6,4,5,3,2,3,1,5,5,4,4,4,8,7,4,6,1,6,4,2,4,3,4,5,9,5,9,8,2,1,2,2,1,5,4,7,6,9,5,6,8,4,6,3,6,9,7,5,5,1,5,5,5,4,4,8,7,6,3,5,1,1,9,8,4,8,4,2,3,2,2,5,8,6,7,6,9,8,8,8,3,3,5,7,7,1,6,5,1,3,9,1,9,3,1,4,4,4,7,1,5,3,1,2,3,7,8,6,9,2,8,9,8,6,6,9,3,8,4,2,1,6,2,2,7,7,4,3,2,6,9,6,3,1,1,8,6,8,2,3,1,2,8,7,7,4,3,4,9,7,4,2,5,2,6,6,1,9,9,5,4,1,2,9,4,2,8,2,9,1,4,7,1,7,7,6,6,5,6,6,7,3,7,8,5,5,9,1,6,9,7,2,7,6,7,8,5,8,4,2,1,7,5,8,4,9,8,2,2,3,4,2,8,8,9,7,3,8,8,4,1,2,8,1,5,7,1,7,1,5,2,8,2,9,9,8,3,6,8,7,5,1,7,1,8,5,3,2,4,2,1,8,5,8,5,5,6,3,7,7,4,1,1,8,7,5,4,5,4,1,7,7,3,3,1,1,7,8,9,8,3,1,4,4,7,2,4,4,8,3,1,1,1,2,3,3,9,1,5,6,5,1,6,4,5,7,7,9,5,5,7,8,6,7,2,6,7,2,6,2,9,2,5,1,8,9,1,9,6,4,4,9,2,9,2,3,5,4,5,2,9,6,9,3,4,6,2,4,3,7,8,3,5,8,8,8,2,3,3,1,8,2,8,1,5,9,5,3,6,3,1,7,1,9,6,8,3,8,3,6,2,6,3,2,7,7,2,7,5,2,2,9,6,7,2,2,4,6,2,2,1,3,3,3,4,3,3,3,5,3,1,6,4,7,9,1,6,9,1,2,5,3,9,2,4,5,1,5,1,7,7,4,6,8,5,6,7,3,1,6,3,4,7,5,6,2,4,3,7,3,3,7,3,5,2,3,7,5,9,9,6,4,3,6,2,6,2,3,9,3,5,3,7,5,3,9,1,5,7,7,6,3,3,9,9,7,2,3,4,5,8,1,5,9,5,7,8,6,3,7,2,3,2,9,9,7,4,4,3,5,6,4,1,9,7,1,7,6,7,2,6,2,4,4,2,6,8,6,4,7,8,2,1,1,2,9,6,6,1,3,6,7,6,1,4,4,2,4,3,5,3,8,9,5,2,9,2,7,4,9,2,7,8,1,2,1,2,8,8,7,6,3,7,2,4,7,2,2,1,4,2,3,9,1,2,6,9,3,6,4,2,8,2,8,8,9,5,9,8,7,2,3,7,3,8,5,4,9,2,2,6,6,8,1,9,4,6,8,7,1,5,9,6,8,4,5,9,6,2,2,9,7,6,3,4,6,5,3,3,6,1,2,6,3,2,6,6,1,4,3,3,1,3,4,4,4,7,9,9,8,3,7,3,7,8,1,5,6,4,5,7,6,2,4,2,9,4,9,1,9,1,7,7,7,8,1,7,6,7,7,1,8,9,7,1,4,1,1,9,2,6,1,5,9,1,6,1,1,8,4,9,4,8,4,8,2,5,4,4,9,8,4,5,2,7,6,3,5,1,3,1,9,2,3,5,6,1,6,8,4,1,1,7,8,1,4,3,4,4,5,4,8,7,7,8,9,7,9,2,9,6,2,3,7,8,1,3,4,9,9,6,1,5,5,3,5,2,2,7,4,8,5,2,7,2,3,9,7,8,5,8,2,1,9,6,1,7,4,8,6,2,6,9,2,1,1,3,6,9,8,4,9,2,7,8,9,9,7,3,8,2,9,5,5,4,8,7,6,6,7,1,2,7,3,5,1,2,8,8,7,9,9,9,3,5,7,4,1,6,6,9,3,1,5,7,9,4,1,9,3,3,5,5,9,7,6,8,3,6,4,8,7,8,9,9,7,9,1,5,9,3,6,1,8,4,6,2,8,7,3,7,4,6,4,3,3,4,4,3,5,8,2,9,3,3,2,9,1,3,6,5,6,1,8,7,5,2,1,3,6,5,2,7,6,2,1,7,1,4,8,1,3,6,2,3,2,9,8,8,2,5,2,8,8,9,9,6,8,3,8,2,1,5,2,2,9,6,7,1,2,7,5,3,3,7,9,5,2,6,8,7,1,6,2,8,5,2,5,8,7,5,9,6,7,3,7,1,7,1,2,7,8,2,9,8,4,1,1,9,6,7,8,5,1,7,6,4,9,5,3,3,1,5,5,3,4,8,3,1,2,5,8,2,2,1,2,6,3,1,2,6,7,1,3,3,7,1,2,7,2,3,8,5,6,6,3,8,3,8,6,6,5,3,1,7,6,5,5,1,8,5,5,9,6,9,5,9,4,3,8,6,6,3,5,8,9,2,4,7,5,7,6,6,6,2,4,3,3,6,7,8,7,6,7,7,7,6,8,8,5,5,4,6,9,1,3,8,5,7,4,1,5,9,3,4,6,4,1,3,6,3,7,6,2,1,4,2,2,8,7,9,7,9,5,4,3,6,5,7,3,7,4,4,7,3,8,5,9,7,2,2,4,9,7,1,1,7,2,3,5,2,4,5,6,2,9,9,9,7,2,5,9,2,5,6,6,2,8,7,5,1,1,4,4,3,5,3,6,4,6,7,4,9,9,2,3,7,5,9,9,8,4,6,4,5,4,7,7,5,9,7,6,3,9,6,6,3,1,6,6,9,7,5,1,7,5,9,3,6,9,1,2,3,9,6,5,2,6,4,3,2,1,4,1,3,7,9,4,1,8,3,6,4,8,6,6,7,6,4,6,1,8,2,9,1,3,7,5,8,6,3,7,3,5,7,2,3,6,6,2,1,5,1,6,1,7,9,9,6,7,4,8,3,5,7,3,8,9,2,2,6,1,8,5,1,7,5,5,7,6,4,4,1,5,8,2,2,7,8,2,9,7,2,2,8,5,8,8,8,7,6,6,5,4,1,8,2,1,4,6,4,9,6,7,6,8,7,7,5,4,4,4,4,3,4,6,4,5,1,1,3,5,9,8,8,7,8,2,1,6,7,8,7,5,1,8,1,7,3,1,2,8,4,6,9,4,4,3,1,3,9,9,1,4,7,1,7,2,4,9,9,4,1,8,2,5,6,7,5,5,1,4,9,5,9,2,3,8,9,9,2,7,5,9,1,7,7,7,3,6,8,8,8,3,8,6,4,3,4,6,4,4,2,4,5,5,1,5,5,6,4,2,9,6,4,5,1,5,5,3,3,2,5,1,8,2,4,9,2,4,9,9,6,1,7,6,5,9,8,5,3,6,4,7,3,8,7,2,9,9,9,5,1,9,1,1,8,5,6,5,9,9,9,5,6,1,7,5,4,1,4,3,4,1,6,5,7,7,2,7,2,8,8,1,5,2,9,7,1,1,2,7,6,9,2,9,9,9,2,6,9,1,9,9,5,4,2,9,9,9,1,5,4,3,2,7,2,7,4,7,9,1,6,3,4,7,8,9,1,5,6,1,8,3,7,4,6,5,1,5,7,6,8,6,2,7,2,9,1,5,9,1,1,4,1,3,6,9,8,9,4,5,8,8,4,1,8,3,4,5,3,6,8,9,8,4,7,2,7,9,9,8,8,3,5,2,8,2,8,1,2,3,7,2,9,1,7,3,9,4,7,6,8,7,4,1,6,2,4,2,8,9,8,7,4,8,3,2,9,6,1,7,5,4,9,7,5,8,4,7,1,4,5,1,9,3,7,4,6,6,2,7,5,7,4,3,3,4,8,6,7,5,6,2,5,2,8,9,8,8,6,4,6,3,8,8,3,5,8,6,4,6,3,1,7,9,6,8,8,1,4,9,7,4,1,7,5,2,6,5,7,1,4,2,4,8,7,9,2,9,1,4,5,8,1,8,3,7,4,8,5,8,2,5,8,3,4,8,5,7,7,1,4,4,9,1,3,4,2,6,6,3,3,8,5,9,9,4,3,6,4,3,1,9,8,8,1,2,7,5,1,6,2,1,5,1,8,1,6,8,2,6,3,3,2,8,1,2,4,9,6,2,1,1,2,8,4,2,8,4,9,9,4,5,8,1,1,6,2,5,1,3,2,6,5,5,8,9,3,4,5,3,2,5,8,4,8,1,5,5,3,1,1,1,9,3,6,7,7,7,7,3,3,9,4,4,1,5,1,3,8,9,5,8,6,4,3,3,3,8,2,1,3,8,9,8,1,7,4,3,7,5,9,2,4,8,9,1,2,4,7,5,7,8,5,5,6,8,4,6,6,6,7,5,2,7,6,4,2,1,1,4,2,8,7,5,5,6,4,7,5,2,2,3,3,3,3,7,3,4,7,8,5,1,3,2,8,5,4,8,5,9,4,8,6,2,3,3,4,4,5,8,4,7,7,4,3,6,4,1,1,2,2,1,1,7,5,5,6,6,7,3,1,4,1,3,2,5,5,4,5,8,1,5,6,7,9,8,5,2,9,6,3,2,2,2,9,3,1,4,6,5,6,3,1,4,4,8,6,2,1,8,1,5,3,3,6,2,7,8,6,6,7,3,9,5,5,4,1,2,6,9,1,8,3,1,6,3,6,3,8,2,7,6,4,7,8,5,4,8,7,8,1,3,4,6,7,3,1,6,3,8,5,4,4,8,8,1,4,1,1,7,4,8,7,3,3,5,3,2,6,5,3,1,2,2,6,7,8,9,5,1,1,2,9,5,7,7,9,4,6,1,2,9,9,4,7,6,5,8,6,7,9,8,9,5,3,5,9,2,7,8,5,9,1,2,8,7,1,3,5,1,8,9,4,4,4,2,3,5,7,4,4,1,5,7,8,3,9,1,9,8,1,8,6,3,8,6,5,8,7,3,9,6,2,6,6,9,7,8,8,4,3,3,3,3,4,2,7,7,2,4,3,4,6,1,6,6,8,3,5,8,7,8,3,5,6,8,7,6,9,5,7,1,6,4,4,8,8,8,8,2,9,4,7,7,4,6,9,2,5,5,2,4,4,8,3,6,3,6,5,2,3,2,9,6,3,9,6,2,3,8,2,3,9,5,9,5,2,3,5,3,4,9,2,6,5,5,6,2,3,5,7,3,5,8,8,7,8,6,5,7,3,5,4,1,7,6,5,8,8,7,3,3,6,4,7,7,7,5,5,4,9,1,4,7,1,4,4,7,3,6,8,8,2,5,5,3,6,4,8,8,3,7,6,4,2,7,1,2,5,6,9,1,7,2,2,2,8,6,9,2,4,7,8,4,9,9,5,2,7,7,2,6,2,1,6,8,5,2,8,1,4,4,4,8,6,5,9,3,7,9,2,1,6,4,6,7,1,3,4,2,5,4,3,5,7,3,8,1,2,6,6,2,2,7,3,2,2,9,8,2,6,2,4,6,3,7,3,1,7,7,1,5,1,4,6,1,6,2,1,9,4,6,9,9,9,5,1,3,2,4,7,4,3,8,5,3,2,4,3,7,4,3,9,8,4,3,5,2,7,7,6,8,7,6,2,1,3,6,5,9,4,7,5,1,7,9,6,8,9,9,4,2,9,5,7,7,1,7,2,3,3,7,9,7,4,4,1,9,8,1,6,4,2,9,3,7,2,9,4,6,8,1,2,8,3,1,4,1,9,5,7,5,2,9,7,8,2,2,5,7,3,9,8,1,4,7,2,8,1,4,8,8,5,7,6,2,2,3,7,7,5,1,1,7,3,6,9,6,3,1,8,2,1,7,7,7,4,7,3,5,3,9,4,2,7,9,9,2,4,6,9,8,7,7,5,9,1,2,3,6,1,2,3,5,7,2,3,7,1,4,4,7,1,7,9,9,6,3,8,2,6,9,9,4,8,1,1,2,4,1,2,6,5,4,4,7,4,5,8,8,6,3,1,3,1,4,6,7,8,4,1,1,3,3,2,4,4,8,6,7,7,6,9,3,8,6,3,2,7,5,1,3,8,4,5,8,8,2,3,1,6,1,8,4,1,1,3,3,9,3,5,3,8,8,3,1,2,6,7,1,6,6,2,5,4,2,2,9,3,8,9,2,4,6,5,6,4,5,9,3,3,7,3,2,6,8,6,4,5,8,3,5,3,9,8,9,2,1,7,5,8,7,6,9,6,5,6,1,7,7,8,2,1,9,1,4,1,8,7,4,9,4,6,3,1,4,3,5,2,4,5,5,6,9,5,1,7,6,6,1,5,2,4,8,9,9,9,4,1,5,2,7,6,6,9,4,8,3,1,1,1,6,9,2,1,4,6,5,2,9,2,6,5,7,4,9,9,8,4,5,1,8,6,6,8,5,2,7,4,8,4,9,2,8,3,3,8,7,9,7,1,4,9,8,8,8,2,3,9,5,3,3,4,3,7,7,9,9,6,7,3,4,7,5,5,4,3,6,3,5,3,4,5,8,9,3,7,1,3,3,1,2,9,3,1,6,5,3,2,8,1,7,7,4,8,4,1,7,8,7,5,1,4,4,9,1,2,3,9,4,1,5,6,9,9,2,9,6,9,3,7,4,5,3,9,3,6,9,6,7,2,4,5,9,7,1,1,6,7,1,9,9,7,5,4,8,5,5,9,9,2,5,8,6,4,4,6,6,9,5,8,5,1,8,8,1,4,8,2,2,9,6,8,5,7,7,6,6,6,1,8,9,1,8,1,7,2,9,2,2,7,2,7,4,8,4,2,3,1,4,5,8,1,9,7,5,8,2,1,3,8,2,8,9,2,7,8,8,7,3,8,4,2,5,1,8,4,4,2,8,1,5,6,2,7,5,1,5,1,2,4,5,6,5,6,6,4,9,1,8,4,6,6,2,5,5,7,4,3,8,9,9,2,8,6,2,6,8,3,5,5,4,4,3,4,9,9,2,4,5,5,6,9,9,9,7,9,4,3,7,9,6,5,2,5,4,8,6,1,4,5,2,6,8,5,4,2,8,4,9,2,6,3,4,2,1,6,2,1,9,2,6,9,4,2,7,5,1,9,6,8,7,4,2,5,5,1,4,3,8,7,3,5,5,4,2,5,3,5,6,3,3,2,8,8,5,8,4,9,2,8,2,1,5,6,3,8,1,6,8,3,6,7,7,7,6,7,3,8,3,5,2,6,1,7,2,1,6,3,1,6,2,6,8,9,6,9,6,4,2,3,8,6,5,9,6,4,5,7,2,7,7,1,6,6,3,8,5,1,9,1,4,8,2,6,7,6,4,4,7,7,5,9,2,5,5,2,8,2,2,1,6,1,9,7,3,2,2,2,6,2,3,5,7,7,9,3,3,2,8,4,8,3,4,1,8,7,9,6,6,9,8,6,6,8,4,7,5,1,8,5,9,3,9,2,8,5,2,1,6,6,6,8,9,4,5,2,6,8,9,3,7,6,4,3,2,5,8,4,6,2,4,8,6,9,3,5,4,7,5,4,5,2,7,7,2,9,2,2,2,5,9,1,1,9,4,9,8,1,3,4,4,5,6,8,5,7,3,3,3,5,2,5,2,2,1,4,4,6,2,2,5,6,6,5,6,2,9,3,9,1,5,8,9,3,4,3,1,1,4,2,9,5,7,7,7,8,6,5,5,1,6,2,6,7,2,7,9,5,3,5,4,8,6,9,3,7,8,1,8,3,4,6,7,4,1,6,8,2,9,2,2,5,5,2,3,7,2,6,3,3,3,5,7,2,8,5,7,4,3,2,9,1,2,6,3,5,4,3,6,2,9,8,2,7,8,8,7,8,2,8,8,4,9,8,3,5,2,6,6,4,9,1,5,7,8,3,5,3,7,8,6,6,6,7,1,3,7,1,9,3,1,1,8,7,2,9,6,2,3,9,2,9,3,7,4,5,2,7,7,2,7,2,9,7,5,2,4,3,7,6,7,3,5,6,1,3,4,5,3,2,4,3,1,4,1,5,6,1,2,7,9,7,2,1,1,1,2,2,2,6,7,6,6,2,8,7,9,7,3,3,6,6,2,6,5,5,1,4,4,1,2,9,1,7,2,5,2,1,2,5,6,6,4,9,1,7,5,1,7,5,4,9,4,4,3,8,2,9,2,1,4,2,8,9,4,7,7,9,3,5,7,9,5,2,5,4,6,2,2,6,1,9,6,7,8,2,9,9,8,7,2,6,4,8,6,8,3,1,4,7,4,3,6,6,9,3,8,3,2,3,2,9,5,1,3,4,1,6,3,7,9,7,4,5,7,1,5,8,8,2,3,3,9,8,7,9,1,2,2,9,1,4,5,9,8,9,5,4,1,4,5,2,6,7,4,2,9,6,3,5,4,1,3,1,2,6,3,7,3,4,6,7,6,7,3,4,1,1,4,2,1,8,9,9,8,5,1,7,9,9,1,4,5,1,1,3,4,9,4,9,6,2,1,8,7,9,8,7,5,8,7,2,6,9,6,7,1,4,4,8,6,7,5,2,7,2,5,9,4,9,5,7,3,1,9,5,1,7,2,2,6,7,3,2,3,2,3,9,8,8,4,9,3,7,3,9,1,6,2,5,4,6,4,8,1,4,9,7,5,3,1,1,7,1,1,8,9,6,7,8,1,8,1,7,6,6,2,5,2,4,6,1,2,3,1,2,8,4,4,9,2,3,1,7,8,8,6,4,5,2,3,8,2,5,4,9,5,1,7,2,4,3,6,3,9,8,5,8,8,4,2,9,3,7,6,1,4,5,8,3,8,6,7,5,4,3,9,8,2,7,7,1,8,4,9,8,5,6,4,3,6,9,4,3,5,8,4,2,1,4,9,3,3,6,3,9,1,7,1,8,8,8,1,9,2,8,9,6,2,3,6,8,1,8,2,5,8,7,9,6,5,9,7,3,1,2,8,7,1,5,5,9,2,6,7,7,2,6,7,4,3,8,9,4,6,9,8,2,9,6,8,6,5,4,7,4,7,5,2,2,5,7,2,9,2,3,4,5,6,5,9,7,5,8,6,2,6,2,1,6,2,9,5,8,5,9,8,8,4,6,6,7,9,8,5,2,1,6,9,8,4,4,9,9,7,7,9,2,1,8,8,7,5,8,5,3,2,8,5,6,9,9,5,4,5,6,6,9,5,9,2,8,4,9,1,7,6,5,4,2,8,8,8,1,3,1,7,5,1,6,8,5,4,3,6,1,6,5,4,3,3,9,9,6,7,6,9,6,8,7,7,5,4,4,1,1,7,9,9,3,5,6,7,5,6,4,7,3,5,5,9,5,3,2,8,4,8,3,7,5,1,3,4,6,8,2,4,2,9,1,3,3,9,2,4,3,3,6,5,4,8,8,7,1,7,6,3,9,3,3,5,5,8,1,6,4,4,1,6,3,8,4,8,7,1,2,4,9,2,1,8,8,2,8,4,9,8,8,1,4,2,2,8,2,5,3,5,1,5,2,7,6,8,8,8,5,2,9,3,3,8,6,1,5,2,2,3,2,9,5,7,2,1,4,7,6,8,4,3,2,2,8,6,3,6,8,2,7,4,3,3,1,5,6,9,6,4,3,3,9,5,6,1,8,1,2,4,7,6,3,4,4,1,4,5,8,6,6,6,7,9,4,9,8,9,6,5,9,9,6,2,3,6,8,6,5,3,6,6,3,8,8,1,3,4,3,8,7,6,4,7,7,3,6,2,2,9,7,2,8,4,5,1,2,2,6,8,3,1,7,1,7,5,8,9,7,4,1,4,5,4,9,8,9,7,6,3,7,2,9,8,3,7,3,5,2,6,6,2,1,9,3,6,2,3,7,4,1,9,8,7,8,9,3,7,6,7,3,6,7,1,6,1,2,5,2,8,1,8,5,4,8,6,8,1,5,6,1,4,5,9,8,1,9,9,2,9,9,4,2,9,1,6,8,9,4,5,2,6,3,1,4,2,2,6,7,8,6,3,8,7,7,3,6,5,2,2,4,3,5,5,9,5,4,8,5,4,4,6,3,5,4,4,3,7,1,5,2,9,2,3,8,6,8,6,1,2,3,7,6,3,4,1,4,4,5,9,9,1,5,5,5,7,4,2,5,4,6,7,2,1,4,5,1,6,6,1,1,5,6,2,4,3,8,5,7,2,1,9,8,4,1,3,5,5,2,1,9,2,1,3,7,4,7,3,3,6,7,2,4,3,7,6,2,9,4,4,1,3,5,7,9,8,9,8,3,6,9,2,9,7,8,8,4,9,3,2,8,8,6,1,3,5,5,9,6,9,2,6,5,9];
Y=[90,447,708,832,473,305,363,538,703,376,497,967,33,921,780,437,945,787,126,87,35,965,951,922,351,734,569,145,619,811,473,987,850,510,831,293,706,980,199,312,918,116,748,525,45,204,22,374,402,566,198,535,835,561,136,582,637,977,676,908,277,675,302,170,650,374,31,751,424,617,903,51,615,82,967,449,101,542,891,542,602,389,543,498,171,962,33,770,197,376,559,127,667,217,816,99,112,768,347,339,818,29,751,935,368,829,854,23,61,79,434,731,384,199,484,965,276,590,791,692,555,522,196,649,220,851,343,917,800,893,91,24,571,111,576,958,43,977,462,212,792,772,83,298,244,885,49,856,959,419,488,104,575,205,426,437,916,789,336,599,277,351,831,382,891,763,895,346,665,226,404,746,590,37,341,224,838,381,218,897,282,925,526,366,977,719,691,419,720,644,808,397,878,35,259,641,310,154,993,464,549,351,367,240,942,585,188,116,197,598,800,432,243,664,542,924,30,50,481,920,609,891,923,580,876,293,135,505,747,331,16,99,248,597,873,869,459,278,487,502,753,39,956,702,432,710,7,648,674,701,199,747,50,39,319,898,772,397,918,150,131,952,106,110,282,764,817,137,255,403,153,83,676,371,296,662,817,1,933,139,357,414,133,41,444,397,183,240,676,171,568,117,883,744,944,469,504,193,432,741,833,910,55,592,198,421,313,588,372,731,653,54,82,512,636,826,828,203,324,333,556,724,10,782,83,853,431,610,590,744,812,413,463,960,128,744,765,988,219,592,3,473,71,945,642,324,416,531,71,383,784,319,314,760,78,270,516,514,263,684,586,795,462,598,536,449,825,307,792,390,139,669,121,678,79,724,369,103,564,82,399,139,734,364,950,115,850,180,403,791,219,864,753,855,386,417,903,728,438,881,282,195,498,541,232,102,566,194,651,636,703,541,46,243,79,590,839,929,877,956,802,997,742,406,958,149,532,268,395,498,353,271,309,248,670,733,980,277,358,833,163,696,109,428,910,414,450,892,884,382,781,463,1,202,141,112,454,154,208,504,225,819,321,869,570,477,522,549,397,319,503,278,675,957,12,438,97,347,687,340,905,45,474,668,62,128,136,958,555,411,95,240,824,327,521,486,202,572,841,266,227,186,516,890,778,75,587,501,337,641,932,3,376,247,814,838,623,839,605,647,186,411,472,622,178,386,390,961,681,421,439,972,720,639,696,863,445,92,904,725,976,191,218,569,798,112,967,455,332,449,817,346,304,178,869,9,451,649,508,566,645,979,198,736,247,712,652,44,215,601,562,648,247,400,951,497,81,645,629,963,721,96,452,48,798,469,695,91,569,133,175,554,824,688,736,485,46,549,439,882,962,315,623,37,614,430,517,199,339,232,257,250,16,798,113,409,468,171,566,1,95,124,570,671,926,982,338,203,749,526,119,656,96,115,751,278,983,458,441,181,750,269,832,159,191,444,57,334,644,531,282,959,927,537,265,453,598,820,630,731,382,567,992,308,68,468,365,614,563,97,586,279,708,52,796,595,675,615,781,459,479,198,74,572,399,901,935,324,997,418,876,689,894,656,944,243,761,703,688,907,661,508,707,677,925,216,826,73,926,115,562,730,515,594,426,726,29,120,783,876,329,511,433,313,30,666,221,352,547,375,167,215,53,368,568,263,55,489,75,565,665,134,65,339,868,22,532,948,289,856,278,909,611,538,636,228,770,904,564,165,393,186,140,945,886,723,640,215,468,374,573,124,680,896,708,115,246,463,590,252,647,359,44,975,45,334,669,399,203,749,356,730,601,424,319,385,368,690,755,360,452,854,868,906,267,700,238,941,622,747,759,345,595,695,138,867,748,428,693,406,427,300,255,940,45,256,539,368,353,483,836,797,509,637,996,880,587,525,859,437,591,425,729,263,293,291,532,150,32,962,549,888,460,695,35,940,262,754,596,74,199,455,889,210,391,386,170,512,843,386,59,222,130,311,711,51,904,796,110,152,614,877,249,133,315,407,282,412,603,573,544,380,847,959,900,176,87,17,878,864,823,4,898,235,856,971,150,285,245,672,792,378,337,651,980,846,504,626,983,59,106,676,99,689,641,207,646,31,416,636,914,636,50,257,560,590,64,357,663,506,845,738,734,193,169,701,29,938,36,829,229,978,123,455,819,91,110,873,34,430,894,441,186,720,573,535,687,813,6,596,665,925,951,56,864,343,54,120,162,897,107,692,384,604,210,931,323,368,373,414,64,434,258,793,111,310,560,729,226,51,688,310,275,721,256,604,610,155,309,6,356,791,36,578,291,695,329,708,837,970,284,412,330,480,232,213,238,222,243,533,148,950,670,517,525,319,498,421,15,902,823,271,837,334,729,769,533,790,815,148,232,867,915,994,344,332,449,229,532,802,585,856,10,758,390,883,91,788,475,374,397,704,27,849,932,537,942,354,476,776,735,924,128,551,494,857,67,455,213,88,956,100,455,568,283,516,721,281,153,887,193,974,307,508,453,102,939,26,372,44,656,109,999,663,658,953,295,548,795,558,651,375,578,422,430,759,743,900,694,50,831,204,368,165,525,129,818,204,621,501,528,855,846,450,37,892,220,713,284,469,38,423,819,689,689,211,450,206,540,554,872,163,261,117,191,73,621,520,839,599,399,463,594,581,760,428,581,443,622,824,863,477,110,643,924,914,770,608,202,216,324,594,390,184,314,543,341,380,736,836,983,421,283,554,936,446,849,601,794,252,230,4,533,739,125,648,762,579,815,248,620,448,451,428,272,790,192,790,895,712,823,128,147,69,277,432,728,86,367,861,910,857,163,826,178,79,617,742,69,445,564,243,194,907,840,916,138,570,422,78,654,755,798,753,27,213,512,600,501,984,994,528,674,152,931,132,103,294,104,205,682,439,309,336,265,306,939,111,369,147,209,604,602,367,662,273,707,974,187,263,349,149,839,339,239,508,200,195,727,663,851,889,84,13,892,878,281,248,4,47,789,407,384,947,880,656,265,728,127,774,452,979,678,291,532,360,610,466,804,261,742,854,180,510,759,44,936,381,687,452,727,976,297,767,293,224,662,197,97,148,710,66,932,698,836,275,681,618,131,516,132,895,535,354,518,486,130,311,436,118,597,273,361,973,713,353,947,358,59,551,650,241,27,559,998,171,68,591,53,357,491,329,676,359,554,748,384,982,977,309,935,289,641,149,163,896,933,810,68,63,797,543,236,29,784,907,535,159,76,26,250,610,584,792,27,709,383,441,495,270,806,435,92,673,618,842,339,770,310,11,854,596,970,293,225,181,458,808,926,154,899,850,885,598,619,967,47,429,38,919,3,729,715,727,456,623,315,312,811,832,236,622,800,18,210,99,36,390,83,829,435,612,925,387,551,604,736,69,433,373,740,572,735,963,797,794,245,419,49,62,24,105,330,15,696,124,296,650,657,286,843,123,486,694,346,851,858,566,567,669,404,137,206,168,837,753,533,486,417,989,372,569,234,137,152,782,35,692,424,821,750,940,170,738,324,505,5,644,646,757,24,791,458,736,780,142,569,531,944,481,433,400,778,113,263,660,409,781,652,185,793,680,844,538,916,774,722,224,937,363,206,922,473,918,221,994,148,813,604,780,88,588,167,29,147,740,413,405,366,448,145,756,834,4,638,677,775,254,794,763,392,730,884,128,177,992,735,613,37,726,837,837,105,273,92,276,976,6,141,266,426,357,726,886,24,593,452,191,240,173,655,251,173,928,826,68,171,850,113,815,785,714,838,511,805,565,569,809,791,492,368,588,702,872,612,668,814,353,6,168,984,988,268,732,971,394,502,315,577,19,312,305,787,497,241,321,834,497,543,878,171,291,973,877,948,457,20,105,139,318,422,41,385,358,484,879,227,47,213,187,974,858,843,239,2,797,632,679,94,664,990,388,432,854,513,242,404,201,782,946,713,925,18,82,78,844,288,722,385,800,337,104,861,424,180,145,550,957,392,397,502,974,191,946,991,473,226,505,318,448,17,109,100,852,541,398,208,551,69,692,680,107,178,711,259,992,190,841,604,218,379,906,706,702,391,272,995,414,426,387,722,959,917,637,930,384,908,613,184,826,147,801,912,752,59,741,955,129,656,830,340,332,941,580,696,137,940,141,871,628,750,148,506,297,479,185,61,503,897,845,926,873,357,157,624,595,871,799,455,975,941,190,113,722,495,322,986,7,645,571,666,362,345,352,975,453,924,637,54,765,644,688,999,974,576,632,867,218,592,730,53,920,544,733,915,146,304,909,246,666,584,221,10,663,444,605,295,193,83,154,860,995,569,467,943,75,149,697,170,197,190,547,764,41,102,283,212,844,338,34,880,526,839,624,20,59,777,412,782,108,366,284,823,795,876,878,654,223,65,938,822,12,322,859,595,706,512,974,555,932,317,624,933,901,848,799,556,707,672,699,970,945,114,255,408,817,435,134,725,802,593,962,849,26,954,225,849,843,527,350,441,97,327,961,265,626,801,725,976,609,194,573,722,724,670,902,958,985,947,57,865,787,988,754,981,613,916,655,40,606,171,819,943,851,906,820,308,156,557,979,992,151,497,265,902,963,815,638,742,368,116,138,234,439,922,766,448,822,440,918,676,851,102,968,697,211,244,237,361,704,530,915,105,361,542,323,879,147,663,544,170,891,821,608,240,183,782,186,553,868,543,750,365,841,730,825,576,32,282,17,670,10,16,777,178,820,274,581,904,104,244,252,83,654,360,603,589,919,245,329,779,144,438,410,583,694,598,83,666,762,127,773,697,756,108,364,234,377,668,731,737,514,808,453,771,218,300,50,402,656,890,833,964,951,715,321,826,225,869,826,612,256,472,626,828,102,21,281,582,56,633,468,929,531,89,157,838,611,154,902,238,420,376,680,650,973,830,899,571,714,943,79,720,529,364,855,872,296,412,643,149,783,495,176,549,444,478,712,648,509,391,768,358,947,478,269,926,324,171,206,107,650,327,220,40,424,810,130,974,375,668,797,414,733,338,741,743,184,190,763,849,97,97,983,304,960,439,3,596,873,112,814,443,643,120,300,311,67,622,915,845,615,352,854,790,319,61,193,850,855,241,376,550,677,929,816,905,58,767,643,357,895,813,640,923,71,368,153,888,808,859,310,775,459,715,537,501,208,239,415,61,764,930,65,184,73,497,244,186,252,960,410,938,213,902,777,549,828,894,735,764,838,346,970,223,869,728,363,333,282,639,635,37,385,74,9,84,255,85,678,166,927,263,998,302,268,57,846,802,741,507,151,752,737,68,862,119,565,516,695,280,195,303,865,708,699,793,523,411,381,831,430,188,330,713,957,426,765,910,271,674,552,257,12,491,864,791,271,726,401,782,151,229,373,265,195,333,124,260,694,963,73,570,452,381,454,928,807,519,15,543,159,674,620,135,122,590,852,973,612,874,954,669,678,661,128,620,797,287,665,450,520,698,356,395,463,752,509,898,766,598,481,898,231,132,607,119,59,935,924,819,37,243,712,732,418,90,267,894,892,829,326,344,201,953,47,950,64,346,52,690,846,804,486,48,442,595,262,307,655,25,752,502,604,309,644,561,496,41,781,360,401,147,612,562,433,686,998,718,754,976,462,326,340,939,890,500,692,672,819,9,257,155,320,857,336,908,807,473,37,705,150,936,570,582,279,78,722,790,541,833,917,111,413,28,434,376,655,861,638,52,190,170,80,671,44,934,682,841,67,544,319,801,668,636,261,659,255,361,226,392,691,667,809,187,376,94,87,386,993,216,148,704,141,454,534,353,329,317,527,731,952,315,437,231,442,402,40,709,608,264,165,803,636,630,624,503,903,53,238,207,168,705,152,106,732,619,704,390,262,660,818,898,699,218,672,771,471,483,327,382,676,675,860,158,522,444,699,219,731,491,579,679,457,391,188,280,210,680,457,629,374,756,135,908,130,424,379,196,701,57,77,751,728,512,707,881,933,591,331,89,335,606,333,268,106,922,97,904,542,727,277,49,684,433,575,912,33,341,38,398,88,761,431,446,800,940,220,442,783,355,395,704,222,510,91,557,665,799,702,506,856,17,871,416,333,730,194,592,197,830,447,902,705,364,665,627,34,34,820,995,657,36,877,702,448,798,638,163,121,468,396,744,176,771,664,304,211,327,685,881,280,464,99,697,154,160,415,416,119,23,673,540,384,690,613,201,969,247,10,723,545,431,505,269,752,124,336,28,966,506,8,191,808,762,537,699,86,760,694,931,758,309,155,251,491,419,182,193,202,525,158,820,72,833,47,369,257,336,451,251,779,158,715,387,304,655,854,422,211,130,457,499,612,842,857,722,199,316,947,268,334,430,834,832,825,739,615,713,510,9,804,723,48,354,179,964,980,419,965,578,369,510,274,929,934,870,107,461,69,867,873,478,945,387,585,138,999,655,308,58,242,699,239,938,693,554,76,138,647,368,207,622,871,199,581,139,901,326,716,446,507,412,470,40,511,505,631,643,123,118,815,681,531,855,989,94,457,516,493,200,681,159,549,532,361,812,342,610,500,121,922,423,157,743,212,372,365,204,769,304,103,743,48,37,256,474,807,993,834,332,397,657,671,394,315,288,251,299,821,564,928,972,652,419,421,968,173,298,205,720,825,373,757,811,444,373,849,546,747,424,433,704,18,885,411,459,332,31,941,104,654,195,976,5,423,610,540,898,752,498,826,398,226,683,708,989,699,865,643,836,736,359,197,270,479,829,880,182,93,991,89,881,882,619,772,310,619,221,363,201,695,865,974,400,67,305,90,99,370,934,172,88,630,761,517,272,990,506,620,750,15,279,678,513,94,627,409,211,740,469,932,907,596,606,38,341,567,312,996,12,708,792,71,592,693,787,521,985,544,770,103,71,449,915,643,971,3,186,204,602,557,958,520,351,253,364,669,26,253,281,304,964,453,98,927,989,526,718,610,547,907,936,782,412,58,368,382,105,482,927,339,50,582,347,554,773,524,475,827,60,17,964,479,388,708,526,949,629,779,442,589,512,642,137,311,73,62,162,543,937,582,298,756,780,341,586,436,42,522,984,93,596,531,412,25,44,531,855,706,260,576,975,382,528,912,174,7,596,964,329,795,33,433,51,242,903,594,268,332,316,26,405,415,287,447,86,707,286,724,715,366,221,652,372,2,664,614,496,508,126,118,633,766,401,973,892,171,735,320,524,513,68,413,592,65,312,646,443,863,339,396,613,782,107,174,423,256,531,491,308,558,893,283,54,617,419,342,17,99,944,472,957,295,832,48,777,197,527,444,343,691,791,512,594,649,600,623,4,482,140,694,852,25,806,397,247,347,276,283,187,126,489,780,104,47,509,317,68,896,528,740,817,250,383,400,901,793,992,320,554,777,543,861,434,202,487,174,466,833,112,136,477,841,502,284,964,555,154,555,610,705,136,837,739,168,341,301,950,287,740,944,350,648,353,247,397,778,549,851,723,576,758,600,737,597,894,337,478,184,625,792,102,272,623,95,578,129,265,482,334,634,339,908,674,365,960,39,883,149,151,289,631,501,584,335,62,583,658,653,302,349,611,42,696,718,870,12,144,835,495,363,576,112,156,285,219,438,21,761,107,719,924,916,962,232,358,451,977,887,764,308,524,968,662,699,647,183,867,76,287,6,619,298,736,447,75,920,937,862,56,805,416,710,524,831,810,892,11,463,811,684,103,204,930,795,782,126,25,200,340,796,586,17,597,63,827,13,788,125,437,141,238,136,820,248,85,746,732,705,680,455,950,155,121,893,917,776,300,854,965,716,864,158,663,643,348,568,285,755,438,962,402,947,369,259,341,821,874,801,279,317,262,643,762,950,485,992,371,306,179,230,976,443,466,825,127,90,183,652,568,582,952,938,951,500,527,87,498,73,929,427,195,880,966,41,853,587,915,566,489,434,513,238,487,130,925,191,790,216,322,729,315,417,279,535,766,502,926,445,767,266,849,249,964,553,875,616,316,858,734,81,798,935,758,855,392,654,15,38,804,982,590,589,350,937,558,739,38,799,211,40,494,281,35,206,345,237,505,278,990,375,670,623,226,941,794,757,112,516,793,703,628,791,484,425,720,741,633,536,504,14,176,305,526,152,979,176,232,178,753,626,122,301,168,50,32,688,551,651,251,833,95,555,693,478,773,357,908,367,213,466,916,607,864,981,779,344,261,917,788,400,217,174,133,919,393,26,257,495,609,236,728,261,634,943,291,701,537,351,133,451,92,834,827,188,243,824,158,678,419,932,402,655,227,45,713,604,689,871,205,672,918,136,737,305,154,585,590,930,963,613,188,481,93,113,129,181,998,559,848,611,102,994,435,663,337,75,930,839,625,38,454,237,253,625,659,821,150,607,179,420,266,758,486,937,267,301,911,329,51,701,627,189,776,798,785,188,149,964,262,463,595,405,19,107,125,497,767,246,919,216,698,192,787,480,776,15,143,595,871,667,664,465,287,412,192,347,469,736,413,23,596,278,176,337,729,761,886,543,655,816,302,456,701,744,845,21,522,899,607,463,677,447,886,173,664,826,152,454,910,403,682,916,876,620,488,537,462,165,692,328,326,321,872,485,690,257,466,296,706,824,436,78,64,964,299,112,882,539,644,256,349,425,404,157,355,741,779,125,780,35,100,421,16,455,421,992,660,302,575,610,595,157,889,653,90,466,552,608,3,226,211,629,73,371,826,15,52,513,890,47,852,324,554,689,714,697,570,233,975,727,303,222,351,731,618,657,445,312,631,274,634,707,16,2,261,510,908,355,184,218,301,990,292,183,21,705,864,14,788,308,463,51,268,629,928,690,158,413,419,91,769,531,926,951,279,483,77,112,656,952,24,252,760,348,977,337,953,817,850,594,746,869,47,604,439,7,199,361,640,855,865,519,498,417,542,476,525,829,44,992,989,943,693,864,449,106,630,570,399,475,716,947,14,530,927,257,240,822,940,703,125,142,871,601,698,928,464,373,370,971,144,932,147,754,160,913,422,476,766,562,589,315,803,967,27,190,884,991,595,274,358,757,960,73,746,346,563,825,784,258,168,699,288,520,154,356,418,292,783,541,436,303,546,84,358,858,507,15,966,114,765,351,21,279,162,770,705,315,638,18,458,957,153,196,944,676,216,330,106,758,147,584,39,540,16,109,152,874,475,860,815,566,282,985,940,92,709,376,12,142,191,936,34,84,317,646,199,600,544,304,766,290,508,940,18,264,50,988,10,30,453,177,325,568,799,790,985,478,183,731,937,128,195,508,905,249,649,446,639,561,604,441,868,520,57,252,247,418,213,83,618,632,912,959,810,427,590,721,505,228,212,992,295,336,492,781,188,96,209,370,575,151,382,61,832,885,205,938,725,444,411,45,75,417,196,21,301,92,761,7,876,74,207,18,5,585,123,732,489,479,653,610,389,354,290,462,690,684,266,547,880,403,480,917,2,90,333,326,557,590,478,451,24,782,555,995,461,157,252,347,907,626,573,680,70,696,477,433,999,227,263,427,621,101,94,563,602,242,579,742,629,632,740,325,716,731,774,139,459,423,405,554,613,338,154,277,955,607,691,154,202,105,761,526,482,492,654,331,996,177,467,651,80,554,626,895,31,241,961,449,716,767,142,355,485,7,421,92,352,988,73,243,321,612,969,880,439,773,184,437,96,620,818,16,794,585,324,687,748,363,798,121,329,255,458,180,135,787,667,560,243,47,129,367,470,594,411,942,46,251,607,775,386,133,802,232,993,767,730,997,583,905,743,451,200,10,568,268,784,724,529,68,234,362,688,320,388,701,228,637,290,234,150,530,338,956,928,826,578,282,985,255,544,223,825,199,225,690,371,745,911,731,726,158,184,288,41,260,216,75,61,873,143,378,221,377,544,408,104,292,724,174,839,786,353,813,290,416,686,382,74,475,305,605,168,413,194,93,737,524,178,939,460,337,306,771,914,995,847,345,215,343,62,877,752,326,175,115,340,779,607,24,796,459,337,96,998,396,592,577,111,991,887,637,994,871,685,841,350,561,540,955,813,317,779,468,234,892,3,66,663,317,268,547,894,740,483,410,483,420,776,869,783,849,727,502,289,457,414,330,831,180,484,48,753,947,791,258,16,79,458,851,555,459,32,994,576,332,202,745,283,203,227,367,4,703,182,645,581,423,610,911,29,964,622,903,401,697,284,307,665,466,282,301,651,194,577,166,349,554,557,313,999,22,511,7,774,740,21,638,482,651,655,665,383,131,832,334,890,552,121,296,468,389,795,879,576,337,503,391,376,981,402,40,108,131,586,561,900,262,694,691,826,657,466,652,7,50,666,856,117,440,850,476,387,883,315,787,40,189,212,784,473,782,79,350,343,336,508,100,267,693,994,721,925,975,468,510,313,517,929,305,375,903,170,215,704,735,107,169,803,324,622,649,844,763,470,484,427,882,826,751,442,384,661,736,415,455,612,409,707,668,957,458,975,699,874,769,654,301,424,499,815,593,775,321,891,96,858,951,331,73,818,957,712,507,14,411,677,692,724,372,720,184,739,131,504,711,762,950,363,48,899,641,182,747,66,958,585,83,714,549,416,976,365,372,103,822,596,297,516,402,880,85,939,945,381,589,473,412,929,285,921,472,289,14,250,104,212,33,75,803,192,688,395,939,602,75,50,759,34,143,624,131,153,986,579,400,900,153,907,337,35,751,676,422,719,710,528,178,442,626,391,790,552,23,191,686,489,28,384,312,731,164,301,378,942,481,467,342,369,477,161,785,38,252,980,961,24,127,186,784,945,180,254,431,42,900,508,569,217,405,104,64,491,450,413,242,935,489,98,248,545,340,552,318,449,402,88,678,375,411,798,864,510,359,990,184,473,307,870,512,346,589,99,450,831,978,950,799,632,505,482,876,650,699,526,838,843,742,412,133,490,590,110,337,265,801,250,139,579,138,767,413,839,989,784,212,670,432,908,241,49,75,438,634,488,558,465,303,844,273,132,621,4,301,260,521,301,324,246,192,447,707,439,933,20,911,408,391,305,41,669,309,593,146,27,292,805,103,727,526,678,616,689,215,135,713,253,492,372,122,692,589,412,459,882,603,142,364,663,979,270,320,713,804,448,919,339,356,636,607,519,796,867,646,456,47,36,965,178,270,414,204,415,940,811,287,196,427,960,592,416,578,724,917,749,964,812,635,883,714,841,743,520,99,680,52,767,266,609,111,526,522,680,284,731,976,155,609,326,311,836,820,710,812,705,396,435,288,74,397,724,815,810,272,569,860,662,445,484,129,617,857,442,604,871,476,374,193,434,40,764,845,299,236,984,128,607,90,567,1,414,753,486,409,847,360,67,475,931,584,512,953,416,885,456,858,82,94,994,924,669,171,207,818,794,54,833,144,768,949,352,530,856,438,845,691,364,968,945,707,626,763,486,426,92,634,902,314,225,328,550,303,318,483,494,2,669,298,827,845,818,81,81,915,582,94,699,45,104,280,435,155,202,976,614,666,738,308,577,561,903,9,206,337,298,62,335,555,107,284,791,589,415,504,837,869,874,779,368,825,170,836,821,478,641,85,149,399,288,993,685,22,178,357,636,930,786,747,875,972,423,667,168,854,967,737,428,648,278,870,904,438,4,736,565,114,203,278,565,982,697,622,196,450,993,106,557,308,883,157,189,436,489,200,283,305,338,823,916,444,30,526,811,583,314,861,448,613,448,708,431,428,378,738,243,640,451,15,437,394,775,972,271,596,116,167,754,751,565,144,390,517,388,540,567,13,907,2,288,615,338,386,814,942,345,623,308,13,110,956,204,736,672,9,490,82,842,357,323,472,823,839,954,263,840,739,906,592,649,258,942,403,525,878,778,952,164,169,80,181,87,120,831,10,31,56,324,912,656,416,578,472,597,859,508,34,397,306,301,146,300,740,815,192,162,623,412,200,453,404,535,992,27,597,332,377,99,973,769,385,209,389,821,629,365,672,906,269,681,697,45,81,908,58,656,47,169,205,461,983,304,444,757,861,16,169,350,204,740,373,421,980,292,299,455,296,374,968,890,568,824,965,423,587,148,996,98,877,598,141,176,811,895,399,46,409,859,199,262,881,746,416,573,951,187,225,247,348,534,364,151,605,866,10,308,974,487,335,401,669,814,386,647,640,199,916,215,795,43,926,414,123,10,398,461,716,678,56,555,943,137,540,99,150,858,211,415,609,509,834,792,963,372,234,152,398,474,795,991,869,458,839,132,16,892,47,119,593,466,416,159,62,470,361,519,747,310,568,472,237,152,486,730,479,342,251,427,851,886,795,442,820,566,348,690,121,585,829,123,949,921,683,231,682,465,678,458,813,605,499,182,573,662,520,148,967,668,853,903,172,451,712,348,369,405,403,205,73,814,370,779,467,987,502,294,977,241,90,934,977,45,644,74,553,745,287,978,409,512,575,302,986,679,849,970,671,644,701,469,43,614,894,521,277,650,275,841,212,773,852,325,196,556,404,587,395,495,794,29,766,360,348,20,158,339,254,251,69,64,987,356,852,108,584,154,532,109,869,158,357,474,315,778,688,292,212,214,935,147,894,307,969,25,699,303,115,667,658,249,6,458,625,998,711,518,164,749,677,689,673,152,207,372,981,928,879,922,776,783,66,810,844,798,52,335,917,949,23,706,660,429,457,761,990,157,283,722,245,804,446,738,63,205,446,526,981,82,743,827,824,508,388,671,907,646,52,715,790,916,267,778,834,123,420,30,371,789,923,390,373,183,138,537,254,600,333,486,955,463,995,58,467,842,743,221,985,258,738,207,685,512,622,903,325,672,577,405,13,153,198,590,494,744,361,224,476,781,451,395,770,815,233,828,467,718,72,567,874,516,979,717,911,273,620,856,171,893,891,366,420,741,829,774,337,94,747,210,745,458,586,193,704,877,806,671,482,435,439,451,499,530,354,61,658,184,832,437,181,849,993,650,651,505,294,585,500,477,853,390,774,192,387,579,660,990,666,565,725,127,744,249,825,534,700,626,653,517,164,44,960,913,393,381,267,855,936,972,267,595,586,877,756,997,926,461,794,231,571,24,556,847,419,410,762,89,944,307,796,58,64,608,611,45,888,19,664,374,122,206,789,670,978,871,998,216,448,638,100,959,187,869,281,371,745,723,588,986,88,778,786,586,535,730,625,60,385,100,609,786,764,888,340,356,450,950,845,626,479,452,763,352,596,532,920,559,983,755,758,187,962,600,392,624,582,692,26,931,214,545,219,256,269,243,839,671,285,46,498,266,465,862,440,548,975,225,914,832,210,927,222,288,589,902,4,884,563,395,540,812,754,146,236,570,770,932,533,218,272,926,724,180,277,446,236,769,14,376,611,132,880,373,3,972,147,268,428,315,740,958,737,683,360,717,442,352,631,890,752,626,761,925,59,612,719,492,16,206,671,65,209,871,296,473,343,384,429,11,268,723,192,442,827,301,7,329,936,774,399,998,783,844,409,137,196,662,513,313,188,838,134,129,804,301,867,662,680,300,79,484,15,380,968,867,461,70,28,663,537,471,981,492,357,906,945,147,256,206,655,99,215,428,521,511,211,899,833,290,619,782,306,243,174,222,958,101,925,572,775,941,783,895,668,245,818,570,673,122,698,113,383,268,178,192,640,656,692,759,174,647,748,553,467,986,736,540,748,146,84,597,907,866,523,679,66,125,980,671,71,330,193,363,115,585,282,360,153,227,288,90,668,322,610,532,369,924,451,502,232,201,705,421,504,533,989,300,555,743,333,283,856,262,930,590,287,394,70,568,899,521,160,265,161,318,284,194,526,165,375,618,982,91,544,64,196,332,124,508,323,496,144,183,583,844,258,57,192,729,524,616,814,794,262,659,845,628,564,377,595,541,401,530,464,764,489,426,46,677,958,330,492,230,206,358,545,91,215,974,598,104,837,108,187,627,839,105,71,823,377,514,798,304,943,129,453,346,198,610,956,966,350,564,123,133,568,139,689,815,157,892,612,337,410,912,339,317,667,545,268,288,44,638,305,364,834,508,931,693,946,862,203,411,60,378,633,599,529,127,127,732,184,563,521,892,580,471,652,91,555,756,571,302,29,91,357,553,500,93,371,207,458,890,995,539,604,457,805,713,906,706,344,521,374,302,36,852,622,40,160,604,310,657,539,666,891,145,350,516,716,905,44,962,936,719,298,578,104,159,324,243,633,606,770,144,658,237,244,523,918,994,285,260,525,186,398,220,814,451,385,789,81,183,662,940,385,234,225,494,349,754,825,496,237,661,978,102,912,819,427,592,413,200,755,544,92,288,990,712,168,285,541,642,389,746,940,627,881,428,238,178,988,683,966,642,486,718,32,479,540,236,281,271,407,517,389,411,877,792,207,415,79,437,212,250,859,669,785,21,356,555,668,558,778,108,502,115,655,410,187,336,581,904,381,277,618,918,516,831,545,717,461,66,383,419,571,334,197,237,319,33,781,224,865,30,712,894,15,725,871,685,616,32,413,390,218,668,92,15,665,804,227,268,96,358,854,846,218,283,582,361,812,516,639,298,12,118,519,199,96,18,36,139,178,601,811,995,429,964,480,809,364,448,312,933,639,794,252,365,790,626,366,942,852,580,170,541,316,853,73,190,456,824,353,856,592,462,822,470,31,724,158,888,973,256,965,476,866,566,926,81,623,913,385,557,870,52,265,938,119,3,640,223,497,444,929,378,505,435,393,741,990,10,169,930,143,370,130,725,101,486,132,301,155,244,445,528,495,128,486,669,709,847,69,901,460,636,969,945,390,108,891,706,610,768,611,442,912,877,580,587,603,350,159,133,484,819,312,480,79,736,122,446,904,733,539,243,543,432,886,406,522,183,189,755,628,393,389,501,880,496,274,560,49,955,274,461,25,628,24,198,313,837,147,431,10,164,102,256,152,241,10,938,344,246,388,455,470,838,348,799,633,796,842,322,700,138,981,743,81,410,588,886,874,830,430,735,312,235,302,866,836,711,518,579,598,784,290,962,831,822,141,43,808,325,270,549,913,360,151,747,645,372,638,535,844,449,352,156,205,707,671,17,952,453,33,288,169,49,711,713,658,260,90,607,614,205,288,25,596,61,833,24,726,245,92,712,837,197,542,657,836,877,800,801,816,742,648,88,992,530,9,552,650,491,552,785,728,950,3,362,51,187,26,510,325,102,719,898,121,998,974,217,166,669,356,704,853,542,602,616,809,697,808,616,703,756,117,817,577,168,236,58,200,405,369,166,457,425,458,630,92,275,796,490,16,25,249,777,118,968,921,102,714,798,4,769,251,303,293,140,888,996,964,303,392,287,841,846,632,446,790,448,416,807,981,453,110,6,659,874,17,801,548,413,292,533,231,842,450,791,314,300,412,934,51,840,687,923,9,851,352,101,83,665,29,401,418,921,443,338,101,278,257,740,975,3,412,627,483,464,466,10,285,151,223,658,103,828,855,62,596,875,885,938,512,316,986,580,973,435,655,237,747,554,70,152,398,110,248,369,170,737,728,863,484,616,110,614,636,177,503,808,74,902,685,798,674,728,289,823,607,629,729,291,412,509,795,533,953,626,706,211,116,220,248,895,919,571,487,451,330,531,714,150,218,743,637,740,611,876,440,713,733,164,865,836,12,475,868,829,837,446,526,945,583,713,31,819,430,421,316,645,62,770,182,733,172,211,83,271,696,408,410,927,928,571,323,289,55,313,376,972,942,681,58,129,654,199,200,60,910,90,565,617,155,292,132,796,883,537,866,414,638,22,176,684,429,319,870,768,23,992,760,946,704,304,585,528,48,498,67,28,392,645,719,724,910,614,224,751,200,935,771,445,168,479,842,166,571,215,942,469,373,241,80,961,765,782,796,512,887,915,497,962,610,76,833,123,64,241,793,859,817,251,305,296,753,920,292,36,497,891,93,974,815,455,135,603,393,3,335,889,508,774,131,140,358,676,763,761,583,623,250,107,518,777,125,97,914,870,399,671,477,643,435,974,339,174,262,668,826,69,830,302,754,507,618,627,963,492,111,135,782,756,744,541,307,239,212,600,150,836,4,20,170,84,695,449,963,521,67,995,391,509,930,287,934,5,24,623,253,910,642,425,283,749,446,440,135,875,495,582,4,85,609,656,132,528,644,535,336,993,466,336,101,103,92,742,271,558,253,179,219,595,96,508,134,650,653,637,916,67,142,540,353,729,468,989,51,268,433,733,713,884,89,556,416,168,149,407,243,825,480,116,118,831,595,835,667,112,677,197,727,368,790,814,347,180,173,75,833,559,190,174,831,330,389,38,608,710,617,586,164,509,498,345,208,478,734,971,654,510,545,159,109,988,112,407,60,49,936,888,734,978,736,752,969,153,247,105,617,798,387,440,558,440,320,357,414,241,3,977,974,923,878,14,839,941,454,827,307,943,315,680,72,315,632,483,141,265,153,513,526,655,273,430,468,206,111,229,243,693,555,918,301,714,897,882,119,841,456,688,81,425,934,810,635,490,398,603,29,589,263,505,164,490,772,981,228,481,497,776,794,758,393,609,678,502,107,40,790,609,863,135,433,970,625,499,13,48,619,981,293,675,210,388,681,281,24,634,749,824,70,948,299,924,90,652,109,500,759,36,322,983,450,239,659,728,105,529,391,40,79,862,18,941,686,217,12,790,255,98,810,641,221,317,62,92,765,45,752,278,680,165,131,591,701,735,233,144,984,783,535,903,546,801,651,455,291,460,11,962,177,660,793,300,982,541,957,537,110,239,854,528,468,4,476,627,664,499,808,952,600,28,655,499,339,243,868,775,196,533,463,480,165,21,215,482,902,91,510,40,46,479,490,686,751,794,815,778,971,390,209,1,818,387,399,614,146,76,784,39,699,468,108,931,762,983,910,800,792,775,50,353,919,548,908,957,139,558,108,761,528,278,446,604,982,866,487,664,366,828,518,318,367,620,521,782,126,925,856,247,627,308,333,956,903,410,9,795,759,287,795,49,847,648,221,978,726,679,696,195,140,457,768,959,104,527,34,257,267,21,517,54,723,739,805,174,974,529,38,989,173,757,809,805,636,281,262,834,223,559,944,691,799,99,146,695,322,524,185,924,310,412,976,993,537,227,722,837,574,795,742,38,943,913,46,667,761,646,43,655,910,498,236,592,271,530,596,794,566,386,264,966,850,481,970,191,174,950,742,938,367,743,472,221,963,368,96,970,665,276,25,671,311,327,601,784,170,649,503,398,631,412,536,110,551,273,7,493,285,90,802,291,838,331,246,526,930,321,756,105,970,320,759,732,69,366,413,560,33,311,57,872,211,891,779,711,810,446,281,331,717,220,790,100,108,819,965,308,323,861,631,570,603,448,911,950,913,196,387,963,705,96,912,847,320,55,281,830,359,204,494,336,761,548,826,79,13,920,296,877,913,723,276,514,549,623,308,169,209,934,946,4,906,602,129,973,130,953,967,758,621,997,777,716,320,458,101,942,822,646,461,429,35,433,286,955,290,553,556,772,357,859,847,901,502,57,603,989,585,77,331,776,703,126,754,571,564,5,668,798,889,850,58,848,980,512,675,370,55,74,829,356,792,523,984,349,613,85,757,313,576,487,550,66,788,849,501,728,2,191,728,297,456,11,33,670,585,297,450,176,938,292,666,170,708,372,617,495,767,6,984,565,269,141,661,393,777,477,422,547,444,3,24,852,440,747,532,711,891,237,604,590,32,261,431,302,882,654,520,134,83,102,192,852,382,74,437,85,448,640,309,191,684,814,787,601,828,921,952,822,580,39,995,922,905,758,941,404,511,985,166,886,725,733,299,730,606,614,609,762,536,446,469,259,786,715,548,383,846,388,826,743,885,33,331,727,34,499,460,918,719,634,392,696,570,102,201,547,639,17,811,991,354,65,966,777,55,390,865,402,169,270,785,891,115,830,370,489,31,255,974,400,161,911,312,899,972,286,703,619,803,182,989,333,942,734,56,101,361,679,762,871,465,929,771,705,717,184,275,445,540,571,32,530,402,503,506,336,968,857,532,33,167,674,170,378,16,305,339,877,481,61,191,675,99,337,813,598,741,141,390,340,185,889,916,421,583,383,596,90,309,761,232,540,349,603,198,581,305,343,955,336,245,31,214,971,982,82,810,625,20,616,888,318,666,851,143,597,343,664,185,515,804,100,936,492,670,891,23,189,307,466,944,273,408,561,9,759,392,864,302,721,900,967,259,766,913,451,294,863,97,13,219,355,68,657,12,777,709,271,899,970,987,389,582,139,394,502,360,223,512,233,695,871,754,809,616,903,639,40,262,899,49,987,976,554,527,730,515,63,181,80,371,118,993,230,55,629,968,229,545,152,7,730,921,946,383,617,9,481,329,256,278,204,938,908,371,991,380,336,951,839,308,806,909,36,716,340,613,676,694,753,364,161,903,200,497,907,495,557,718,360,601,865,961,485,845,158,420,389,252,896,626,989,953,961,856,825,458,110,950,512,550,722,706,13,417,144,150,601,835,493,322,868,727,199,290,910,98,247,462,200,605,640,632,575,242,878,105,342,161,665,687,726,925,27,950,984,6,746,303,824,109,825,167,482,145,495,440,336,631,471,306,574,516,667,642,82,193,400,793,404,465,488,557,988,903,488,632,957,383,685,834,212,393,823,649,123,563,456,153,26,340,421,295,837,721,139,9,737,117,305,506,317,756,906,653,122,164,401,358,853,479,71,60,325,87,660,775,98,186,596,934,268,697,275,625,570,120,747,166,793,420,281,867,881,381,610,632,851,265,820,254,149,748,990,686,322,673,737,699,312,814,833,517,213,247,826,142,312,589,960,522,99,884,454,173,102,405,870,56,859,835,240,379,23,9,680,265,163,333,170,818,929,923,581,601,718,126,850,946,909,855,922,88,424,138,82,583,178,528,204,917,284,317,983,725,654,920,855,379,583,872,190,393,681,563,769,962,241,624,260,554,366,209,918,499,541,884,983,816,636,985,858,176,944,759,585,274,506,889,506,364,916,777,962,282,690,3,652,84,134,956,874,388,430,961,385,701,291,918,508,851,185,183,470,870,826,41,56,238,706,139,523,828,754,785,664,178,210,404,344,719,818,309,907,795,463,141,211,236,152,227,377,382,483,702,496,434,618,624,725,575,790,610,121,683,586,805,751,267,691,778,826,220,392,407,700,24,135,209,199,964,957,746,676,379,418,273,807,126,774,35,234,402,411,61,939,112,514,43,307,275,298,686,197,303,64,881,115,820,612,852,344,885,539,765,69,288,743,470,223,628,828,20,511,186,440,830,719,359,81,540,319,233,957,720,912,903,296,121,481,367,781,141,349,196,778,297,1,878,669,855,665,41,400,486,185,957,486,185,35,701,552,909,684,228,386,934,279,730,853,996,786,722,769,262,723,335,118,546,750,154,13,623,62,407,568,671,793,781,736,85,725,452,382,643,209,704,603,231,680,17,478,40,517,272,301,149,213,586,36,444,463,901,193,167,208,558,588,394,854,794,740,899,262,265,870,696,293,835,448,77,903,778,668,315,837,115,770,529,937,765,220,578,777,715,134,318,581,966,985,209,109,118,56,629,876,238,293,45,946,14,707,555,426,256,520,952,506,227,154,991,687,563,762,50,804,226,112,519,738,386,395,606,844,898,125,465,555,511,72,744,342,825,188,428,274,902,869,287,777,430,793,433,359,384,222,25,535,454,630,647,413,572,495,713,45,893,755,342,987,263,291,210,855,547,263,108,182,675,539,667,250,576,42,556,363,956,823,198,547,601,376,921,107,952,421,665,336,831,597,125,923,50,683,862,710,476,889,362,430,79,89,958,423,520,894,416,162,1,431,792,762,944,102,86,775,818,626,7,284,224,607,432,823,331,14,831,827,865,238,178,551,595,491,663,284,390,245,97,255,477,987,200,521,462,452,489,355,899,124,776,886,17,707,917,260,385,421,780,368,137,601,542,429,956,440,677,618,458,526,723,207,469,692,725,211,599,207,204,300,905,611,784,276,990,773,305,540,45,742,11,351,201,468,910,1,226,834,278,689,349,700,160,865,191,412,996,248,38,38,920,200,368,873,581,633,742,303,292,825,493,120,998,685,520,139,478,304,90,929,177,320,332,820,789,823,881,489,747,71,614,706,265,375,624,463,584,718,123,258,902,911,462,819,292,913,817,434,67,874,550,490,837,769,465,589,545,870,337,653,298,970,903,916,650,659,845,54,76,641,286,626,167,275,904,849,930,754,660,522,897,948,767,143,261,820,450,814,942,837,454,204,224,937,784,632,796,861,19,843,943,262,110,447,603,54,689,878,652,235,712,556,165,790,858,898,16,914,392,613,645,489,361,685,901,886,785,121,578,569,264,956,64,841,950,169,558,367,743,649,970,975,696,860,725,148,614,705,693,852,437,956,116,350,94,939,972,257,728,380,265,879,349,276,286,403,304,155,121,714,941,996,286,300,90,905,924,951,806,752,510,533,952,951,630,723,38,484,411,775,182,572,183,98,188,518,443,231,176,904,847,95,784,646,799,413,819,804,946,428,190,550,433,745,962,570,713,850,961,692,635,459,528,893,603,326,703,143,375,900,973,303,854,184,649,295,700,176,454,420,108,567,340,664,34,770,754,412,226,142,908,314,627,273,557,856,157,474,851,211,141,610,772,939,54,28,236,289,830,661,254,770,659,625,820,113,535,292,462,742,30,478,830,564,47,766,461,148,500,629,608,717,183,887,676,879,837,689,841,327,197,626,68,496,546,324,586,452,486,850,407,866,804,910,527,971,767,100,89,838,159,225,920,949,735,567,529,385,426,136,250,832,422,8,964,863,8,585,764,53,335,640,491,353,38,26,594,461,507,245,314,313,195,687,433,177,359,68,560,204,908,323,804,955,969,220,26,43,431,617,187,68,48,832,274,643,701,123,186,254,996,875,6,960,365,18,808,535,938,182,840,113,227,765,32,286,210,767,797,370,742,869,909,125,490,778,568,870,844,925,372,621,90,516,834,205,710,845,478,186,713,297,292,793,240,729,647,911,737,61,32,867,776,80,120,939,947,831,839,93,780,409,889,601,466,917,364,956,933,112,21,603,723,644,496,79,277,421,245,511,403,925,649,344,355,354,943,499,110,947,597,599,232,477,761,904,853,86,867,803,603,753,833,930,113,985,342,21,323,487,203,403,658,995,636,184,674,222,188,887,468,447,175,819,682,19,416,659,629,317,171,660,156,508,752,362,985,466,993,96,591,278,254,517,309,585,771,481,844,987,103,254,594,685,724,980,894,759,913,187,547,140,453,962,327,331,18,236,24,917,701,499,874,898,253,729,293,835,207,761,746,681,395,812,555,602,345,7,78,726,708,847,323,465,198,780,37,145,96,287,404,344,989,687,974,116,867,121,364,156,249,225,834,154,45,18,328,915,431,822,733,524,338,945,668,982,474,920,13,674,232,661,772,314,616,326,511,387,931,269,870,235,894,89,665,120,891,174,76,584,61,477,478,139,914,727,96,846,834,53,134,114,671,688,493,156,900,562,215,225,545,350,631,67,567,401,11,445,800,147,842,285,372,277,984,871,452,606,136,984,510,841,898,202,574,430,87,597,997,483,375,229,294,347,226,570,435,974,134,469,960,842,50,942,750,747,498,388,529,939,503,209,638,707,795,198,512,520,916,328,606,509,488,614,69,490,500,227,599,347,828,867,21,621,7,40,460,154,882,684,757,958,591,114,836,22,722,724,432,117,449,769,423,575,127,973,152,859,834,369,151,772,716,333,996,305,605,73,433,51,625,161,111,237,710,52,714,451,476,733,233,636,548,302,356,258,531,475,157,304,35,446,617,334,681,284,823,907,347,352,998,401,747,889,305,208,985,525,270,133,926,20,55,839,854,822,239,100,817,326,900,181,906,207,283,844,473,677,509,367,426,215,131,87,22,508,665,244,830,465,226,759,890,664,671,480,937,199,446,735,416,825,368,651,956,30,143,318,943,588,730,867,200,455,69,830,869,284,880,153,488,455,690,820,473,685,195,309,336,758,390,326,681,214,982,116,267,538,63,28,485,176,701,792,965,877,858,51,532,819,349,702,224,10,317,977,186,481,75,641,542,832,721,939,147,485,130,547,147,77,311,983,644,101,174,476,978,834,191,671,968,269,780,171,91,827,738,54,711,100,614,38,883,10,364,847,992,868,368,137,722,16,211,841,940,243,235,146,871,347,273,5,746,756,629,10,293,530,811,861,749,25,103,257,762,927,515,19,242,94,104,659,564,617,280,844,301,169,757,96,747,273,391,523,784,222,156,3,788,94,535,253,525,957,564,800,512,573,84,254,867,474,792,741,815,86,209,904,758,733,351,352,326,202,176,994,367,65,664,459,795,266,601,175,468,119,442,118,832,894,212,769,76,176,795,936,615,33,91,294,833,814,320,760,970,598,262,479,357,77,7,181,933,556,856,302,699,683,766,608,535,356,729,852,208,675,97,273,224,492,116,489,346,552,334,286,803,103,913,55,320,771,23,884,311,46,887,241,705,782,389,346,147,442,122,898,945,576,152,932,554,887,511,112,357,693,399,656,486,605,314,486,892,944,241,505,573,673,957,738,115,778,188,778,533,718,605,823,983,259,363,456,312];